package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.Stack;

/**
 * todo
 *
 * @author wanwei
 * @since 2022-03-18 17:37
 */
public class AW97交错字符串 {

    public static void main(String[] args) throws InterruptedException {
        System.out.println(isInterleave("12222211"
                , "211112211111", "12222221111112211111"));
    }


    /**
     * 动态规划
     *
     * 如果dp(i-1,j) = true && s1(i) = s3(i+j)  || dp(i,j-1) = true && s2(j) = s3(i+j)
     * @param s1
     * @param s2
     * @param s3
     * @return
     */
    public static boolean isInterleave2(String s1, String s2, String s3){
        int n = s1.length(), m = s2.length(), t = s3.length();

        if (n + m != t) {
            return false;
        }

        boolean[][] f = new boolean[n + 1][m + 1];

        f[0][0] = true;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                int p = i + j - 1;
                if (i > 0) {
                    f[i][j] = f[i][j] || (f[i - 1][j] && s1.charAt(i - 1) == s3.charAt(p));
                }
                if (j > 0) {
                    f[i][j] = f[i][j] || (f[i][j - 1] && s2.charAt(j - 1) == s3.charAt(p));
                }
            }
        }
        return f[n][m];
    }

    /**
     * 使用两个指针分别指向两个字符串
     * 先走A指针 A指针不匹配时 B指针前进  B指针不匹配时 A指针前进 如果A也不匹配 则B回退 再使A前进 直到能继续匹配字符为止
     * 使用栈记录AB交换时的坐标
     *
     * 有bug 暂未找出来
     *
     * @param s1
     * @param s2
     * @param s3
     * @return
     */
    public static boolean isInterleave(String s1, String s2, String s3) throws InterruptedException {
        if (s1.length() == 0) {
            if (s2.equals(s3)) {
                return true;
            } else {
                return false;
            }
        } else if (s2.length() == 0) {
            if (s1.equals(s3)) {
                return true;
            } else {
                return false;
            }
        } else if (s3.length() == 0) {
            return false;
        }
        Stack<int[]> stack = new Stack<>();
        int index1 = 0;
        int index2 = 0;
        int index3 = 0;
        Boolean flag = true;
        if (s1.charAt(0) == s3.charAt(0)) {
            index1 = 1;
            index3 = 1;
            flag = true;
        } else if (s2.charAt(0) == s3.charAt(0)) {
            index2 = 1;
            index3 = 1;
            flag = false;
        }
        Boolean entryFlag = true;

        //当全部退到原点时 表示匹配不成功 循环结束 失败！
        while ((index1 > 0 || index2 > 0) && index3 <= s3.length() - 1) {
            if (flag) {
                if (entryFlag) {
                    //前进
                    if (index1 < s1.length() && s1.charAt(index1) == s3.charAt(index3)) {
                        index1++;
                        index3++;
                        flag = true;
                        entryFlag = true;
                    } else if (index2 < s2.length() && s2.charAt(index2) == s3.charAt(index3)) {
                        index2++;
                        index3++;
                        flag = false;
                        entryFlag = true;
                        if (index1 != 0 && index2 != 0) {
                            stack.add(new int[]{index1, index2});
                        }
                    } else {
                        entryFlag = false;
                    }
                } else {
                    //后退  直到B符合 或者到交换节点或者直接到0
                    while (true) {
                        if (stack.isEmpty()) {
                            index1--;
                            index3--;
                            //可以等于0 相当于起点切换到B
                            if (index1 < 0) {
                                break;
                            }
                            if (s2.charAt(index2) == s3.charAt(index3)) {
                                index2++;
                                index3++;
                                flag = false;
                                entryFlag = true;
                                if (index1 != 0 && index2 != 0) {
                                    stack.add(new int[]{index1, index2});
                                }
                                break;
                            }
                        } else {
                            int[] arrays = stack.peek();
                            if (arrays == null || arrays[0] < index1) {
                                index1--;
                                index3--;
                                if (index2 < s2.length() && s2.charAt(index2) == s3.charAt(index3)) {
                                    index2++;
                                    index3++;
                                    flag = false;
                                    entryFlag = true;
                                    if (index1 != 0 && index2 != 0) {
                                        stack.add(new int[]{index1, index2});
                                    }
                                    break;
                                }
                            } else if (arrays[0] == index1) {
                                //最近交换节点丢掉 并将指针切到B 继续后退
                                stack.pop();
                                index1--;
                                index3--;
                                flag = false;
                                entryFlag = false;
                                break;
                            }
                        }
                    }
                }
            } else {
                if (entryFlag) {
                    //前进
                    if (index2 < s2.length() && s2.charAt(index2) == s3.charAt(index3)) {
                        index2++;
                        index3++;
                        flag = false;
                        entryFlag = true;
                    } else if (index1 < s1.length() && s1.charAt(index1) == s3.charAt(index3)) {
                        index1++;
                        index3++;
                        flag = true;
                        entryFlag = true;
                        if (index1 != 0 && index2 != 0) {
                            stack.add(new int[]{index1, index2});
                        }
                    } else {
                        entryFlag = false;
                    }
                } else {
                    //后退  直到B符合 或者到交换节点或者直接到0
                    while (true) {
                        if (stack.isEmpty()) {
                            index2--;
                            index3--;
                            //如果字符2被推到0 则肯定不可能匹配了 此时不结束的话 就会继续切换到字符1 无限循环下去
                            if (index2 == 0) {
                                break;
                            }
                            if (s1.charAt(index1) == s3.charAt(index3)) {
                                index1++;
                                index3++;
                                flag = true;
                                entryFlag = true;
                                if (index1 != 0 && index2 != 0) {
                                    stack.add(new int[]{index1, index2});
                                }
                                break;
                            }
                        } else {
                            int[] arrays = stack.peek();
                            if (arrays == null || arrays[1] < index2) {
                                index2--;
                                index3--;
                                if (index1 < s1.length() && s1.charAt(index1) == s3.charAt(index3)) {
                                    index1++;
                                    index3++;
                                    if (index1 != 0 && index2 != 0) {
                                        stack.add(new int[]{index1, index2});
                                    }
                                    flag = true;
                                    entryFlag = true;
                                    break;
                                }
                            } else if (arrays[1] == index2) {
                                //最近交换节点丢掉 并将指针切到A 继续后退
                                index2--;
                                index3--;
                                stack.pop();
                                flag = true;
                                entryFlag = false;
                                break;
                            }
                        }
                    }
                }
            }
        }

        if (index3 == s3.length() && s1.length() == index1 && s2.length() == index2) {
            return true;
        }
        return false;
    }

}